from BD_grid_recursion import TransBD, BD_2D_LEVELS_SIZE

class LineSegmentBD:
    """
    北斗线段类：仅含折线拆分与网格相交判断两个核心函数
    """
    EPS = 1e-12  # 容差：避免浮点误差导致边界误判

    def __init__(self, lat1=None, lon1=None, lat2=None, lon2=None):
        self.lat1, self.lon1 = lat1, lon1
        self.lat2, self.lon2 = lat2, lon2

    # 折线拆分函数
    @staticmethod
    def from_polyline(points):
        """
        将折线点集拆分成多个 LineSegmentBD 线段对象
        """
        if not points:
            return []
        if len(points) == 1:
            lat, lon = points[0]
            return [LineSegmentBD(lat, lon, lat, lon)]
        return [LineSegmentBD(points[i][0], points[i][1], points[i+1][0], points[i+1][1])
                for i in range(len(points) - 1)]

    # 线段与指定网格相交判断函数
    def intersects_grid(self, grid_code: str, level: int, bd: TransBD) -> bool:
        """
        判断该线段是否与指定北斗网格相交
        """
        lat_min, lon_min = bd.bd2d_to_coordinates_level(grid_code, level)
        dx, dy = BD_2D_LEVELS_SIZE[f"Level_2D_{level}"].value
        lat_max, lon_max = lat_min + dy, lon_min + dx

        # 快速排除：线段外接矩形与网格不重叠
        if (max(self.lat1, self.lat2) < lat_min or
                min(self.lat1, self.lat2) > lat_max or
                max(self.lon1, self.lon2) < lon_min or
                min(self.lon1, self.lon2) > lon_max):
            return False

        # 任一端点在格内（包含左下角，排除右上角）
        def point_in_cell(lat, lon):
            return (lat_min <= lat < lat_max) and (lon_min <= lon < lon_max)

        if point_in_cell(self.lat1, self.lon1) or point_in_cell(self.lat2, self.lon2):
            return True

        # 检查与矩形四条边是否相交
        def ccw(A, B, C):
            return (C[1] - A[1]) * (B[0] - A[0]) > (B[1] - A[1]) * (C[0] - A[0])

        def segments_intersect(A, B, C, D):
            return (ccw(A, C, D) != ccw(B, C, D)) and (ccw(A, B, C) != ccw(A, B, D))

        def intersection_point(A, B, C, D):
            (x1, y1), (x2, y2) = (A[1], A[0]), (B[1], B[0])
            (x3, y3), (x4, y4) = (C[1], C[0]), (D[1], D[0])
            denom = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)
            if abs(denom) < 1e-18:
                return None
            px = ((x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)) / denom
            py = ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)) / denom
            return (py, px)

        edges = [
            ((lat_min, lon_min), (lat_min, lon_max)),
            ((lat_max, lon_min), (lat_max, lon_max)),
            ((lat_min, lon_min), (lat_max, lon_min)),
            ((lat_min, lon_max), (lat_max, lon_max)),
        ]

        for e1, e2 in edges:
            if segments_intersect((self.lat1, self.lon1), (self.lat2, self.lon2), e1, e2):
                inter = intersection_point((self.lat1, self.lon1), (self.lat2, self.lon2), e1, e2)
                if inter is None:
                    return True  # 共线算相交
                plat, plon = inter
                if point_in_cell(plat, plon):
                    return True
        return False

    @staticmethod
    def trace_polyline_grids(polyline, level, bd: TransBD):
        """
        给定折线，返回其经过的指定级别网格码集合（递推法实现）。
        """
        if not polyline:
            return set()

        all_grids = set()
        segments = LineSegmentBD.from_polyline(polyline)

        for seg in segments:
            crossed = bd.get_line_crossed_grids_fast(seg.lat1, seg.lon1, seg.lat2, seg.lon2, level)
            all_grids.update(crossed)

        return sorted(all_grids)





# ---------------- 测试示例 ----------------
"""
通过设置级数生成对应级数折线穿过的网格的对应级数网格码
"""
# if __name__ == "__main__":
#     bd = TransBD()
#     # polyline = [
#     #     (12, -6),
#     #     (0, 0),
#     #     (8, 12)
#     # ]
#     # polyline = [
#     #     (0, 0),
#     #     (0, 6),
#     #     (4, 12),
#     #     (12, 18),
#     # ]
#     polyline = [
#         (0, 0),
#         (-12, 6),
#         (0,18)
#     ]
#     level = 1
#
#     grids = LineSegmentBD.trace_polyline_grids(polyline, level, bd)
#     print(f"折线经过 {len(grids)} 个 {level} 级网格：")
#     for g in sorted(grids):
#         print(g)
import csv
"""
生成制定折线指定级数网格对应的网格码csv文件
"""
if __name__ == "__main__":
    bd = TransBD()
    # 可自定义折线坐标点
    polyline = [
        (0, 0),
        (-12, 8),
        (0,18)
    ]

    # 指定网格级数
    level = 1
    # 输出文件名
    output_csv = f"BD_Level_{level}_grids.csv"

    # 获取折线经过的所有网格码
    grids = LineSegmentBD.trace_polyline_grids(polyline, level, bd)
    print(f"折线经过 {len(grids)} 个 {level} 级网格，正在写入文件...")

    # 写入 CSV 文件
    with open(output_csv, "w", newline='', encoding="utf-8") as f:
        writer = csv.writer(f)
        writer.writerow(["grid_code"])  # 表头

        for idx, g in enumerate(sorted(grids)):
            writer.writerow([g])

            # 可选：每 1000 条输出一次进度
            if (idx + 1) % 1000 == 0:
                print(f"已处理 {idx + 1} 条...")

    print(f"完成！输出文件：{output_csv}")